//
// Created by BWY on 2024/2/24.
//
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>

using namespace std;

// 2583. 二叉树中的第 K 大层和
// 给你一棵二叉树的根节点 root 和一个正整数 k 。
//树中的 层和 是指 同一层 上节点值的总和。
//返回树中第 k 大的层和（不一定不同）。如果树少于 k 层，则返回 -1 。
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode():val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x):val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right): val(x), left(left), right(right) {}
};
class Solution {
private:
    void dfs(TreeNode* root, int level, vector<long long>& sums) {
        if(root == nullptr) return;

        if(level >= sums.size()) {  // 新的一层
            assert(level == sums.size());
            sums.push_back(root->val);
        } else
            sums[level] += root->val;

        dfs(root->left,level+1,sums);
        dfs(root->right,level+1,sums);
    }
public:
    long long kthLargestLevelSum(TreeNode* root, int k) {
        vector<long long> sums;
        dfs(root,0,sums);
        sort(sums.begin(),sums.end(),greater<>());
        return k - 1 < sums.size() ? sums[k-1] : -1;
    }
};
int main() {
    TreeNode* root1 = new TreeNode(5,
                                   new TreeNode(8,
                                                new TreeNode(2,new TreeNode(4),new TreeNode(6)),
                                                new TreeNode(1)
                                   ),
                                   new TreeNode(9,new TreeNode(3),new TreeNode(7))
    );
    cout << Solution().kthLargestLevelSum(root1,2) << endl; // 13
    return 0;
}

